#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7+10,M = 3010;
int t,n,m,v[M][M],o,mi,ans,f[N],cnt,sum;
struct w
{
	int u,v,w;
}a[N];
int find(int x)
{
	if(f[x] == x) return x;
	return f[x] = find(f[x]);
}
inline bool cmp(w x,w y){return x.w<y.w;}
signed main()
{
	freopen("up.in","r",stdin);
	freopen("up.out","w",stdout);
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld%lld",&n,&m); ans = 0;
		if(m == 0) 
		{
			printf("%lld\n",n-1);
			continue;
		}
		if(n <= 3000)
		{
			for(int i = 1;i <= n;i++)
				for(int j = i+1;j <= n;j++)
					v[i][j] = 0;
			for(int i = 1;i <= m;i++)
				scanf("%lld%lld%lld",&a[i].u,&a[i].v,&a[i].w),v[a[i].u][a[i].v] = 1;
			cnt = m;
			for(int i = 1;i <= n;i++)
				for(int j = i+1;j <= n;j++)
					if(!v[i][j])
						a[++cnt].u = i,a[cnt].v = j,a[cnt].w = j-i;
			for(int i = 1;i <= n;i++) f[i] = i;
			sort(a+1,a+1+cnt,cmp);
			o = ans = 0;
			for(int i = 1;i <= cnt;i++)
			{
				if(o == n-1) break;
				if(find(a[i].u) != find(a[i].v)) f[a[i].u] = find(a[i].v),o++,ans += a[i].w;
			}	
		}
		else 
		{
			for(int i = 1;i <= m;i++)
				scanf("%lld%lld%lld",&a[i].u,&a[i].v,&a[i].w);
			ans = n-1; sum = 0;
			for(int i = 1;i <= m;i++) 
				if(a[i].u == a[i].v-1)
				{
					if(a[i].w == 0) ans--;
					else sum++;
				}
			ans += sum/2;
		}
		printf("%lld\n",ans);
	}
	return 0;
}


